Міністерство науки і освіти України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра програмного забезпечення
Звіт з лабораторної роботи №12
з дисципліни “Алгоритми і структури даних ”
Виконав:
студент групи ПІ – 1
Львів 2008
Тема роботи: Алгоритм побудови бінарного дерева згортання
Мета роботи: Вивчити та дослідити методи обробки даних. Ознайомитись із алгоритмом побудови бінарного дерева згортання. Виконати лабораторну роботу використавши здобуті знання з методів обробки даних, зокрема алгоритму побудови бінарного дерева згортання.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Необхідно побудувати дерево згортання Т(Х, F) графу. Множина вершин Х графу належатимуть до 1-го рівня дерева згортання, приймемо Х1 = Х. На першому кроці в множині Х2 маємо групи з двох елементів, для яких функція критерію F приймає екстремальне значення. Утворені групи належать до множини 2-го рівня дерева згортання. На другому кроці формується множина Х3 3-го рівня з елементів множини Х1 і Х2 . Процес продовжується до утворення множини Хk , яка складається з одного елемента – кореня дерева згортання.
Алгоритм А
А1. Для всіх хi, хj є Х1 визначити функцію критеріюF(хi, хj);
А2. Об‘єднати пари елементів хk, хt з найкращим значенням функції критерію F і виключити їх зі списку елементів – кандидатів на об‘єднання.
Приклад роботи алгоритму побудови бінарного дерева згортання представлено на рис. 1.
SHAPE \* MERGEFORMAT
d a b a a a
e e c c b b
f f e d c d
adef
abcde
abcdef
abcd
abcd
2
2
3
3
2
2
2
2
2
2
Рис. 1. Дерево згортання.
Текст програми
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
#include<math.h>
#define N 25
struct S* create(int);
struct S* create(struct S*, struct S*,float);
void clean(struct S*);
void find(struct S*, int);
int kryterij(struct S*, struct S*);
int average(struct S*, struct S*);
/*-Struktura-*/
struct S
{
int a; //Vlasne znachenna
struct S* left; //Vk. na livogo syna
struct S* right; //Vk. na pravogo syna
};
//-----------------------------------
void main()
{
clrscr();
int i, r, j, h=N;
int ix, jx, sumx;
int mas[N];
/*-Inicializacija-*/
for (i=0;i<N;i++)
mas[i]=rand()%41;
/*-Pobudova dereva-*/
S* pmas[N]; //Vk. na vershyny
for(i=0;i<N;i++)
pmas[i]=create(mas[i]);//Budujemo riven structur
while(h>1)
{
sumx=32767;
for(i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
if(pmas[i]!=NULL&&pmas[j]!=NULL)
if(kryterij(pmas[i],pmas[j])<sumx)
{
sumx=kryterij(pmas[i],pmas[j]);
ix=i;
jx=j;
}
pmas[ix]=create(pmas[ix],pmas[jx],sumx);
pmas[jx]=NULL;
h--;
}
find(pmas[0],0);
clean(pmas[0]);
getch();
}
//------------------------------------
/*-Stvorenna vershyn nyzchogo rivn'a-*/
struct S* create(int a)
{
struct S* b=(struct S*)malloc(sizeof(struct S));
b->a=a;
b->left=NULL;
b->right=NULL;
return b;
}
/*-Stvorenn'a vershyn vyschyh rivniv-*/
struct S* create(struct S* a, struct S* b, float sumx)
{
struct S* c=(struct S*)malloc(sizeof(struct S));
c->left=a;
c->right=b;
c->a=sumx;
return c;
}
/*-Ochyschenna pam'jati-*/
void clean(struct S* b)
{
if(b->left!=NULL)
delete(b->left);
if(b->right!=NULL)
delete(b->right);
free(b);
}
int kryterij(struct S *b, struct S *c)
{
return (int)sqrt(pow(b->a-20,2)+pow(c->a-20,2));
}
void find(struct S* b, int depth)
{
for(int i=0;i<depth;i++)
printf(" ");
printf("%i\n", b->a);
if(b->left!=NULL) find(b->left, depth+1);
if(b->right!=NULL) find(b->right, depth+1);
}
int average(struct...
